// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package trace

import (
	"math"
	"sort"
)

// mud是一个可更新的突变子利用率分布。
// 
// 这是突变子
// 利用率的持续时间分布。例如，从突变子利用率a 
// 到b的积分是在[a，b]范围内，突变子利用率为
// 的总持续时间。
// 
// 此分布*未*规范化（它不是概率
// 分布）。随着
// 的更新，这使其更易于使用。
// 
// 表示为标度均匀分布
// 函数和狄拉克三角函数之和（被视为
// 退化均匀分布）。
type mud struct {
	sorted, unsorted []edge

	// trackMass是更新分布时要跟踪的反向累积和。
	trackMass float64
	// trackBucket是指轨道质量下降的铲斗。如果分布的
	// 总质量<trackMass，则这是
	// len（hist）。
	trackBucket int
	// trackSum是hist[：trackBucket]的累积和。一旦
	// trackSum>=trackMass，必须重新计算trackBucket。
	trackSum float64

	// hist是分布质量的分层直方图。
	hist [mudDegree]float64
}

const (
	// mudDegree是泥浆总结中的桶数
	// 柱状图。
	mudDegree = 1024
)

type edge struct {
	// 在x处，函数增加y。
	x, delta float64
	// 另外，x处是一个面积为Dirac的Dirac delta函数。
	dirac float64
}

// add在[l，r]标度上添加一个统一函数，因此统一的总重量
// 为面积。如果l==r，则添加一个狄拉克增量函数。
func (d *mud) add(l, r, area float64) {
	if area == 0 {
		return
	}

	if r < l {
		l, r = r, l
	}

	// 添加边。
	if l == r {
		d.unsorted = append(d.unsorted, edge{l, 0, area})
	} else {
		delta := area / (r - l)
		d.unsorted = append(d.unsorted, edge{l, delta, 0}, edge{r, -delta, 0})
	}

	// 更新直方图。
	h := &d.hist
	lbFloat, lf := math.Modf(l * mudDegree)
	lb := int(lbFloat)
	if lb >= mudDegree {
		lb, lf = mudDegree-1, 1
	}
	if l == r {
		h[lb] += area
	} else {
		rbFloat, rf := math.Modf(r * mudDegree)
		rb := int(rbFloat)
		if rb >= mudDegree {
			rb, rf = mudDegree-1, 1
		}
		if lb == rb {
			h[lb] += area
		} else {
			perBucket := area / (r - l) / mudDegree
			h[lb] += perBucket * (1 - lf)
			h[rb] += perBucket * rf
			for i := lb + 1; i < rb; i++ {
				h[i] += perBucket
			}
		}
	}

	// 更新质量跟踪。
	if thresh := float64(d.trackBucket) / mudDegree; l < thresh {
		if r < thresh {
			d.trackSum += area
		} else {
			d.trackSum += area * (thresh - l) / (r - l)
		}
		if d.trackSum >= d.trackMass {
			// 跟踪质量现在落在不同的
			// 桶中。重新计算逆累积和。
			d.setTrackMass(d.trackMass)
		}
	}
}

// setTrackMass设置要跟踪的反向累积和的质量。
// 
// 具体来说，mass是一个累积持续时间，可以使用
// 使用范围。
// ApproxinCumulativeSum查询该持续时间的变异子
func (d *mud) setTrackMass(mass float64) {
	d.trackMass = mass

	// 通过计算累计和
	// 找到当前包含trackMass的bucket。
	sum := 0.0
	for i, val := range d.hist[:] {
		newSum := sum + val
		if newSum > mass {
			// 桶i中的质量下降。
			d.trackBucket = i
			d.trackSum = sum
			return
		}
		sum = newSum
	}
	d.trackBucket = len(d.hist)
	d.trackSum = sum
}

// approxInvCumulativeSum类似于invCumulativeSum，但具体而言，
// 对跟踪质量进行操作，并返回逆累积和的上限和下限
// 近似值。
// 
// 真正的逆累积和将在[下限，上限]范围内。
func (d *mud) approxInvCumulativeSum() (float64, float64, bool) {
	if d.trackBucket == len(d.hist) {
		return math.NaN(), math.NaN(), false
	}
	return float64(d.trackBucket) / mudDegree, float64(d.trackBucket+1) / mudDegree, true
}

// invCumulativeSum返回x，使得d的整数从-∞ to x 
// 是y。如果d的总重量小于y，则返回分布的最大值
// 为false。
// 
// 具体地说，y是一个累积持续时间，invCumulativeSum 
// 返回至少y个时间具有
func (d *mud) invCumulativeSum(y float64) (float64, bool) {
	if len(d.sorted) == 0 && len(d.unsorted) == 0 {
		return math.NaN(), false
	}

	// 对边进行排序。
	edges := d.unsorted
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].x < edges[j].x
	})
	// 与已排序的边合并。
	d.unsorted = nil
	if d.sorted == nil {
		d.sorted = edges
	} else {
		oldSorted := d.sorted
		newSorted := make([]edge, len(oldSorted)+len(edges))
		i, j := 0, 0
		for o := range newSorted {
			if i >= len(oldSorted) {
				copy(newSorted[o:], edges[j:])
				break
			} else if j >= len(edges) {
				copy(newSorted[o:], oldSorted[i:])
				break
			} else if oldSorted[i].x < edges[j].x {
				newSorted[o] = oldSorted[i]
				i++
			} else {
				newSorted[o] = edges[j]
				j++
			}
		}
		d.sorted = newSorted
	}

	// 按顺序遍历边以计算累计和。
	csum, rate, prevX := 0.0, 0.0, 0.0
	for _, e := range d.sorted {
		newCsum := csum + (e.x-prevX)*rate
		if newCsum >= y {
			// y在前一条边
			// 与此条边之间超出。
			if rate == 0 {
				// 在prevX和
				// e.x就可以了。我们返回e.x 
				// 因为这会处理
				// y==0的情况。
				return e.x, true
			}
			return (y-csum)/rate + prevX, true
		}
		newCsum += e.dirac
		if newCsum >= y {
			// y被e.x上的狄拉克增量超过了。
			return e.x, true
		}
		csum, prevX = newCsum, e.x
		rate += e.delta
	}
	return prevX, false
}
